package interview.tree;

import algorithm.model.TreeNode;

/**
 * Leetcode 112
 * 路径总和
 * 给一个二叉树和一个target,
 * 判断这个树中，是否存在根节点到【叶子节点】的路径，使得路径相加的和等于target
 *
 * 注意：是叶子节点。即没有子节点的node
 *
 * Created by yzy on 2021-02-07 14:58
 */
public class PathSum {

    /**
     * 思路：递归
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        if(root.left==null && root.right==null && root.val==targetSum){
            return true;
        }
        int nextTarget = targetSum - root.val;
        return hasPathSum(root.left, nextTarget) || hasPathSum(root.right, nextTarget);
    }
}
